class Node{//节点
    constructor(element){
        this.element = element;
        this.left = null;//左
        this.right = null;//右
    }
}

class Tree{//树  二叉树
    constructor(){
        this.root = null;
    }
    //插入节点
    insert(element){
        let newNode = new Node(element);//创建新节点
        if(this.root === null){//树中没有任何元素
            this.root = newNode
        }else{
            //递归
            this.insertNode(this.root,newNode)
        }
    }
    insertNode(node,newNode){
        if(newNode.element < node.element){//如果新节点的值小于根节点  左边
            if(node.left === null){//没有值了
                node.left = newNode
            }else{//下面还有值
                this.insertNode(node.left,newNode)
            }
        }else{//右边
            if(node.right === null){//没有值了
                node.right = newNode
            }else{
                this.insertNode(node.right,newNode)
            }
        }
    }
    //先序
    preOrderTraverse(){
        this.preOrderTraverseNode(this.root);
    }
    preOrderTraverseNode(node){
        if(node!=null){
            console.log(node.element);
            this.preOrderTraverseNode(node.left);
            this.preOrderTraverseNode(node.right);
        }
    }
    //中序
    midOrderTraverse(){
        this.midOrderTraverseNode(this.root);
    }
    midOrderTraverseNode(node){
        if(node!=null){
            this.midOrderTraverseNode(node.left);
            console.log(node.element);
            this.midOrderTraverseNode(node.right);
        }
    }
    //后序
    postOrderTraverse(){
        this.postOrderTraverseNode(this.root);
    }
    postOrderTraverseNode(node){
        if(node!=null){
            this.postOrderTraverseNode(node.left);
            this.postOrderTraverseNode(node.right);
            console.log(node.element);
        }
    }
    max(){//求最大值
        let current = this.root;
        while(current!=null&& current.right){
            current = current.right;
        }
        return current
    }
    //查询
    search(element){
        return this.searchNode(this.root,element)
    }
    searchNode(node,element){
        if(node==null){
            return false//未查找到要寻找的值
        }
        if(node.element>element){//左边查找
            return this.searchNode(node.left,element)
        }else if(node.element<element){//右边查找
            return this.searchNode(node.right,element)
        }else{
            return true//查找到要寻找的值
        }
    }
    min(){//求最小值
        this.minNode(this.root)
    }
    minNode(node){
        let current = node;
        while(current!=null&& current.left){
            current = current.left//current = current.next
        }
        return current
    }
}
let tree = new Tree();
// 使⽤BST 二叉树数据结构将图⽚中的数据插⼊其中 
tree.insert(11);
tree.insert(7);
tree.insert(5);
tree.insert(9);
tree.insert(3);
tree.insert(8);
tree.insert(10);
tree.insert(15);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);
console.log(tree.min())
console.log(tree.max())
console.log(tree);
